SieveOfEratosthenes.java

packageLecture9;

// finds all prime numbers between 2 and n in O(log(log n))

publicclassSieveOfEratosthenes {

publicstaticvoidmain(String[] args) {

intn = 30;

soe_find_primes(n);
 }

publicstaticvoidsoe_find_primes(intn) {
boolean[] primes = newboolean[n + 1];

for (inti = 0; i < primes.length; i++) {
primes[i] = true;
 }

intnum = 2;

while (num * num < n) {
if (primes[num]) {
for (intmultiplier = 2; num * multiplier <= n; multiplier++) {
primes[num * multiplier] = false;
 }
 }
num++;
 }

for (inti = 2; i < primes.length; i++) {
if (primes[i]) {
System.out.print(i + " ");
 }
 }
 }
}